package com.example.leetcode.day;

import java.util.Stack;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/decode-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Day394 {

    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i = 0;i<s.length();i++) {
            char c = s.charAt(i);
            if (c != ']') {
                stack.add(c);
            }else {
                String s1 = get(stack);
                int num = getNum(stack);
                while (num > 0) {
                    for (int j =0;j<s1.length();j++) {
                        stack.add(s1.charAt(j));
                    }
                    num--;
                }

            }
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }



    private int getNum(Stack<Character> stack) {
        if (stack.isEmpty()) {
            return 0;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty() && stack.peek() - '0' >=0 && stack.peek() - '0' <=9) {
            sb.append(stack.pop());
        }
        return Integer.parseInt(sb.reverse().toString());
    }

    private String get(Stack<Character> stack) {
        StringBuilder sb = new StringBuilder();
       while (!stack.isEmpty() && stack.peek() != '[') {
           sb.append(stack.pop());
       }
       stack.pop();
       return sb.reverse().toString();
    }

    public static void main(String[] args) {
        Day394 d = new Day394();
        String s = "abc3[cd]xyz";
        System.out.println(d.decodeString(s));
    }
}
